package 数组题目.前缀和与差分;

import java.util.HashMap;

//和为k的子数组
//https://leetcode.cn/problems/subarray-sum-equals-k/
class 和为k的子数组 {
    //给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。
    //子数组是数组中元素的连续非空序列。
    public int subarraySum(int[] nums, int k) {
        //用hashmap存每一个 numSum[i]- k 的值个数，如果存在则 +1，反之添加到索引
        HashMap<Integer, Integer> indexMap = new HashMap<>(nums.length);
        int[] numSum = new int[nums.length + 1];
        indexMap.put(0, 1);
        int res = 0;
        for (int i = 1; i < numSum.length; i++) {
            numSum[i] = nums[i - 1] + numSum[i - 1];
            int need = numSum[i] - k;
            // 如果之前存在值为 need 的前缀和
            // 说明存在以 nums[i-1] 结尾的子数组的和为 k
            if (indexMap.containsKey(need)) {
                res += indexMap.get(need);
            }
            // 将当前前缀和存入哈希表
            indexMap.put(numSum[i], indexMap.getOrDefault(numSum[i], 0) + 1);
        }
        return res;
    }

    public static void main(String[] args) {
        System.out.println(new 和为k的子数组().subarraySum(new int[]{1, 1, 1}, 2));
//        System.out.println(new Solution().subarraySum(new int[]{1, 2, 3}, 3));
//        System.out.println(new Solution().subarraySum(new int[]{1}, 0));
    }
}
